/* 
 * Unique Paths
 */

#include "../func.h"

int uniqPaths(int m, int n)
{
    if (m < 1 || n < 1)
        return 0;
    if (1 == m && 1 == n)
        return 1;
    return uniqPaths(m - 1, n) + uniqPaths(m, n - 1);
}

int uniquePaths(int m, int n)
{
    vector<vector<int>> f;
    f = vector<vector<int>>(m, vector<int>(n, 0));
    f[0][0] = 1;
    return dfs(m - 1, n - 1, f);
}

int dfs(int x, int y, vector<vector<int>> &f)
{
    if (x < 0 || y < 0)
        return 0;
    if (0 == x && 0 == y)
        return f[0][0];

    if (f[x][y] > 0)
    {
        return f[x][y];
    }
    else
    {
        return f[x][y] = dfs(x - 1, y, f) + dfs(x, y - 1, f);
    }
}

//f[i][j] = f[i-1][j] + f[i][j-1]
int dp(int m, int n)
{
    vector<int> f(n, 0);
    f[0] = 1;
    for (int i = 0; i < m; ++i)
    {
        for (int j = 1; j < n; ++j)
        {
            f[j] = f[j] + f[j + 1];
        }
    }
    return f[n - 1];
}

//Math